#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self , arr ):
        # write code here
        if not arr:
            return []
        subSequence = [arr[0]]
        maxLen = [1]  # 每个位置为终点的LIS长度，初始值为1
        for i in range(1, len(arr)):
            # 判断递增，当前数对应的最长递增序列长度+1
            if arr[i] > subSequence[-1]:
                subSequence.append(arr[i])
                maxLen.append(len(subSequence))
            else:
                # 二分搜索当前比新数大的最小值用来记录当前数对应的最长递增序列
                low, high = 0, len(subSequence)
                while low < high:
                    mid = (high - low) // 2 + low
                    if subSequence[mid] >= arr[i]:
                        high = mid
                    else:
                        low = mid + 1
                # 用新值取代大于新值的最小值
                subSequence[low] = arr[i]
                # 记录对应当前数组元素的当前最长子序列的长
                maxLen.append(low + 1)
        # subSequence不一定是字典序最小
        i = len(arr) - 1
        k = len(subSequence) - 1
        while k >= 0:
            # 相同的值靠后的字典序小
            # 所以从后往前遍历
            # 长度为1的数放到位置0
            if maxLen[i] - 1 == k:
                subSequence[k] = arr[i]
                k -= 1
            i -= 1
        return subSequence
